/*
 * Project: Sudoku Explainer
 * Copyright (C) 2006-2007 Nicolas Juillerat
 * 
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.generator;

import java.util.List;
import java.util.Random;

import com.onegravity.sudoku.solver.HintEngine;
import com.onegravity.sudoku.solver.SolvingTechniquesConfig;
import com.onegravity.sudoku.solver.checks.SolutionProducer;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.ExtraRegionType;
import com.onegravity.sudoku.solver.data.Grid;

public class Generator {

    private final SolutionProducer solutionProducer = new SolutionProducer(true);
    private boolean isCancelled = false;
    
    /**
     * Generate a Sudoku grid matching the given parameters.
     * <p>
     * Depending on the given parameters, the generation can take very
     * long. The implementation actually repeatedly generates random
     * grids with the given symmetries until the difficulty is between
     * the given bounds.
     * @param symmetries the symmetries the resulting grid is allowed to have
     * @param minDifficulty the minimum difficulty of the grid
     * @param maxDifficulty the maximum difficulty of the grid
     * @return the generated grid
     */
    public Grid generate(List<Symmetry> symmetries, double minDifficulty, double maxDifficulty, ExtraRegionType extraRegions,
    					 byte[][] blockCodes, int maxNrOfAttempts, int maxNrOfIterations, int maxNrOfGivens) {
    	if (symmetries.isEmpty()) symmetries.add(Symmetry.None);
        Random random = new Random();
        int symmetryIndex = random.nextInt(symmetries.size());
        while (true) {
            //System.out.print(".");
            // Generate a random grid
            Symmetry symmetry = symmetries.get(symmetryIndex);
            symmetryIndex = (symmetryIndex + 1) % symmetries.size();
            Grid grid = generate(random, symmetry, extraRegions, blockCodes, maxNrOfAttempts, maxNrOfIterations, maxNrOfGivens);
            if (isCancelled || grid==null) return null;
            
            // check for maximum number of givens
            int nrOfGivens = 0;
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                	if (grid.getCellValue(x, y)>0) nrOfGivens++;
                }
            }

            if (nrOfGivens<=maxNrOfGivens) {
                // Analyse difficulty
                Grid copy = new Grid(grid);
                grid.copyTo(copy);
                copy.rebuildPotentialValues();
                HintEngine solver = new HintEngine(new SolvingTechniquesConfig(), copy, false, null);
                double difficulty = solver.analyseDifficulty(minDifficulty, maxDifficulty);
                if (difficulty>=minDifficulty && difficulty<=maxDifficulty) {
                    //System.out.println("difficulty: " + difficulty);
                	grid.setDifficulty(difficulty);
                    return grid;
                }
                else {
                	//System.out.println("difficulty: " + difficulty + " is outside of defined range");
                }
            }

            if (isCancelled) return null;
        }
    }

    /**
     * Generate a random grid with the given symmetry
     * @param rnd the random gene
     * @param symmetry the symmetry type
     * @return the generated grid
     */
    private Grid generate(Random rnd, Symmetry symmetry, ExtraRegionType extraRegionsType, byte[][] blockCodes, int maxNrOfAttempts, int maxNrOfIterations, int maxNrOfGivens) {

		// Build the solution
        Grid grid = new Grid(extraRegionsType, blockCodes!=null, blockCodes);
        
        boolean resultOK = false;
		try {
			long l = System.currentTimeMillis();
	    	//System.out.println("starting solutionProducer()");
	    	resultOK = solutionProducer.solve(grid, rnd, maxNrOfIterations);
	    	grid.setAll2Givens();
	    	//System.out.println("solutionProducer() took " + (System.currentTimeMillis()-l)/1000f + " seconds");
	    	if ((System.currentTimeMillis()-l)>10000) {
	    		resultOK = false;
	    	}
		}
		catch (InterruptedException ignore) {
			// ignore the interruption, we use a different mechanism to stop the generator
		}
		
		if (!resultOK) return grid;
		
        Grid solution = new Grid(extraRegionsType, blockCodes!=null, blockCodes);
        grid.copyTo(solution);

        // Build running indexes
        int[] indexes = new int[81];
        for (int i = 0; i < indexes.length; i++)
            indexes[i] = i;
        // Shuffle
        for (int i = 0; i < 81; i++) {
            int p1 = rnd.nextInt(81);
            int p2 = rnd.nextInt(81);
            int temp = indexes[p1];
            indexes[p1] = indexes[p2];
            indexes[p2] = temp;
        }

        int attempts = 0;

        // Randomly remove clues
    	//System.out.println("removing clues...");
        boolean isSuccess = true;
        while (isSuccess) {
            // Choose a random cell to clear
            int index = rnd.nextInt(81);
            int countDown = 81; // Number of cells
            isSuccess = false;
            do {
                // Build symmetric points list
                int y = indexes[index] / 9;
                int x = indexes[index] % 9;
                Point[] points = symmetry.getPoints(x, y);

                // Remove cells
                boolean cellRemoved = false;
                for (Point p : points) {
                    Cell cell = grid.getCell(p.x, p.y);
                    if (cell.getValue() != 0) {
                        cell.setValue(0, false);
                        cellRemoved = true;
                    }
                }
                if (cellRemoved) {
                    // Test if the Sudoku still has an unique solution
                    int state = -1;
					try {
						//long l = System.currentTimeMillis();
				    	//System.out.println("starting getCountSolutions()");
						state = solutionProducer.getCountSolutions(grid, maxNrOfIterations);
				    	//System.out.println("getCountSolutions() counted " + state + " solutions");
				    	//System.out.println("getCountSolutions() took " + (System.currentTimeMillis()-l)/1000f + " seconds");
					}
					catch (InterruptedException neverHappens) {
						// ignore the interruption
						// we use a different mechanism to stop the generator
					}
                    if (state == 1) {
                        // Cells successfully removed: still a unique solution
                        isSuccess = true;
                    }
                    else {
                        // Failed. Put the cells back and try with next cell
                        for (Point p : points) {
                            grid.setCellValue(p.x, p.y, solution.getCellValue(p.x, p.y), true);
                        }
                        attempts += 1;
                        if (attempts==maxNrOfAttempts) return grid;
                    }
                }
                index = (index + 1) % 81; // Next index (indexing scrambled array of indexes)
                countDown--;
            } while (!isCancelled && !isSuccess && countDown > 0);
        }
        return grid;
    }

    public void cancel() {
        isCancelled = true;
    }

}